package cmich.cps.scheduler.algorithms;

import java.text.ParseException;
import java.text.SimpleDateFormat;
import java.util.ArrayList;
import java.util.Date;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.logging.Logger;

import javax.swing.SwingWorker;

import cmich.cps.scheduler.data.AssignedCourse;
import cmich.cps.scheduler.data.Course;
import cmich.cps.scheduler.data.Preference;
import cmich.cps.scheduler.data.Professor;
import cmich.cps.scheduler.data.Room;
import cmich.cps.scheduler.data.Schedule;
import cmich.cps.scheduler.gui.Frame;
import cmich.cps.scheduler.gui.Prompts;

/**
 * The Class Algorithm.
 *
 * @author Jonathan Kissinger <kissi1j@cmich.edu>
 */
public abstract class Algorithm extends SwingWorker<Void,Void> {

	/** The Constant LOGGER. */
	protected final static Logger LOGGER = Logger.getLogger(KruskalBased.class.getName());

	/** The prompts. */
	protected Prompts prompts = Prompts.getInstance();

	/** The system. */
	protected AlgorithmSystem system = new AlgorithmSystem();

	/** The validator. */
	protected Validator validator = new Validator(system);

	/** The processing progress. */
	protected int processingProgress;

	/** The schedule being processed. */
	protected Schedule schedule;

	/** The processing total. */
	protected int processingTotal;

	/** Fast mode. */
	protected boolean isFastMode;

	/** The counter. */
	protected long counter;

	/** The seed. */
	protected long seed = 0;

	/** The best schedule. */
	protected Schedule bestSchedule = null;

	/** The max. */
	protected int max;

	/** The algorithm name. */
	protected String algorithmName = null;

	/**
	 * Start the algorithm.
	 */
	abstract void start();

	/**
	 * Generate a schedule.
	 */
	protected void generateSchedule() {
		this.processingTotal = system.getCourses().size();
		this.processingProgress = 0;
		schedule = new Schedule();
		schedule.setAlgorithmUsed(algorithmName);
		schedule.setValue(0);
		schedule.setTimestamp(validator.getTimestamp());
		schedule.setTheoreticalMax(max);
		manuallyAssignCourses();
		updateProgress();
		while(system.getCourses().size()>0 && !isCancelled()) {
			HashMap<String, Integer> courseValues = new HashMap<String, Integer>();
			List<Preference> coursePreferences = setCourseNegativePreferenceValues();
			for(int i=0;i<coursePreferences.size();i++) {
				Preference negativePreference = coursePreferences.get(i);
				Course course = (Course) system.getObject(negativePreference.getItem(), system.getCourses());
				Preference preference = setProfessorValues(course);
				if(preference!=null) {
					courseValues.put(preference.getItem(), preference.getValue() + negativePreference.getValue());
				}
			}
			List<Preference> courseTies = getHighestValueKeys(courseValues);
			if(courseTies.size()==0) {
				schedulingFailure();
				return;
			}
			else {
				assign(breakTies(courseTies, "overall"));
			}
		}
		schedule.setValue(getScheduleValue(schedule));
	}

	/**
	 * Sets the fast mode.
	 */
	protected boolean setIsFastMode() {
		for(int i=0;i<system.getProfessors().size();i++) {
			Professor professor = system.getProfessors().get(i);
			if(!professor.getTimeBetweenCourses().equals("No preference")) {
				return false;
			}
		}
		return true;
	}

	/**
	 * Adds up all negative preferences for all courses.  This is the score that
	 * would be earned by assigning this course, with the exception of the score
	 * of the professor that it is assigned to.
	 *
	 * @return the list
	 */
	protected List<Preference> setCourseNegativePreferenceValues() {
		LOGGER.finer("Setting negative course preference values.");
		List<Preference> coursePreferences = new ArrayList<Preference>();
		for(Course course : system.getCourses()) {
			Preference coursePreference = new Preference();
			coursePreference.setItem(course.getSectionNumber());
			coursePreference.setValue(0);
			int value = 0;
			for(int i=0;i<system.getProfessors().size();i++) {
				Professor professor = system.getProfessors().get(i);
				value = system.getPreferenceValue(professor, course.getName());
				if(value < 0) {
					value = Math.abs(value) + coursePreference.getValue();
					coursePreference.setValue(value);
				}
			}
			coursePreferences.add(coursePreference);
		}
		LOGGER.finer("Finished setting negative course preference values.");
		return coursePreferences;
	}

	/**
	 * Processes a scheduling failure.
	 */
	protected void schedulingFailure() {
		for(Professor professor : system.getProfessors()) {
			if(professor.getAssignedCourses()<professor.getMaxCourses()) {
				LOGGER.finer("Remaining professors " + professor.getName());
			}
		}
		for(Course course : system.getCourses()) {
			LOGGER.finer("Remaining course: " + course.getName());
		}
		for(Room room : system.getRooms()) {
			if(!room.getLab()) {
				String msg = "Remaining timeslots for room: " + room.getName();
				for(String timeslot : room.getTimeslots()) {
					msg = msg + "\n" + timeslot;
				}
				LOGGER.finer(msg);
			}
		}
		LOGGER.info("Error: No available assignments for remaining courses.");
	}

	/**
	 * Checks to make sure a professor isn't already teaching a course at the
	 * given timeslot.
	 * 
	 * @param professor The professor to check.
	 * @param timeslot The timeslot to check.
	 * @return true if there is no conflict, false if there is a conflict
	 */
	protected boolean checkTimeslot(Professor professor, String timeslot) {
		for(AssignedCourse assignedCourse : schedule.getCourses()) {
			if(assignedCourse.getTimeslot().equals(timeslot) && professor.getName().equals(assignedCourse.getProfessor())) {
				return false;
			}
		}
		return true;
	}

	/**
	 * Gets the next tie, given the current {@link #counter} value.
	 *
	 * @param ties the ties
	 * @return the next tie
	 */
	protected Preference getNextTie(List<Preference> ties) {
		if(ties.size()==0) {
			return null;
		}
		long index = counter;
		if(counter>=ties.size()) {
			index = counter % ties.size();
			counter = counter - index;
			counter = counter / ties.size();
		}
		else {
			counter = counter - index;
		}
		LOGGER.finest("Tie Breaker Choice: " + index);
		Preference preference = ties.get((int) index);
		return preference;
	}

	/**
	 * Checks all professors for a given course, first checking that the professor has not
	 * exceeded the maximum courses. Then checking each professor's room/timeslot combos.
	 * Once a best room timeslot combo is found, that value is added to the professor's preference
	 * for the given course and saved in the hashmap with the course, professor, room and timeslot
	 * (delimited by "::") as the key. Finally the professor with the highest value for the
	 * given course is returned.
	 * 
	 * @param course The course to find a value for
	 * @return A <code>Preference</code> with the name of the professor as the item
	 */
	protected Preference setProfessorValues(Course course) {
		HashMap<String, Integer> professorValues = new HashMap<String, Integer>();
		List<Professor> professors = new ArrayList<Professor>();
		for(Professor professor : system.getProfessors()) {
			if(professor.getAssignedCourses()<professor.getMaxCourses()) {
				professors.add(professor);
			}
		}
		for(int i=0;i<professors.size();i++) {	
			Professor professor = professors.get(i);
			Preference preference = getBestRoomTimeslotCombo(professor, course);
			if(preference!=null) {
				int value = system.getPreferenceValue(professor, course.getName()) + preference.getValue();
				String key = course.getSectionNumber() + "::" + professor.getName() + "::" + preference.getItem();
				professorValues.put(key, value);
			}
		}
		List<Preference> professorTies = getHighestValueKeys(professorValues);
		return breakTies(professorTies, course);
	}

	/**
	 * Gets the best room timeslot combo.
	 *
	 * @param professor the professor
	 * @param course the course
	 * @return a <code>Preference</code> representing the best room timeslot combination
	 */
	protected Preference getBestRoomTimeslotCombo(Professor professor, Course course) {
		List<Preference> roomTimeslotsTies = getHighestValueKeys(getRoomTimeslotMap(professor, course));
		return breakTies(roomTimeslotsTies, professor);
	}

	/**
	 * Break ties.
	 *
	 * @param ties the ties
	 * @param object the object
	 * @return the preference
	 */
	protected Preference breakTies(List<Preference> ties, Object object) {
		String name = object.toString();
		Preference preference = new Preference();
		String item = "";
		Integer value = 0;
		if(ties.size()==0) {
			return null;
		}
		if(ties.size()==1) {
			item = ties.get(0).getItem();
			value = ties.get(0).getValue();
			LOGGER.finer("Best for " + name + " is " + item + " for " + value);
		}
		else {
			String msg = ties.size() + " way tie found.";
			LOGGER.finest(msg);
			Preference tieBreaker = null;
			if(object instanceof String) {
				tieBreaker = overallTiebreaker(ties);
			}
			if(object instanceof Course) {
				tieBreaker = courseTiebreaker(ties);
			}
			if(object instanceof Professor) {
				Professor professor = (Professor) object;
				tieBreaker = professorTiebreaker(professor, ties);
			}
			item = tieBreaker.getItem();
			value = tieBreaker.getValue();
		}
		preference.setValue(value);
		preference.setItem(item);
		return preference;
	}

	/**
	 * Overall tiebreaker.
	 *
	 * @param ties the ties
	 * @return the preference
	 */
	protected Preference overallTiebreaker(List<Preference> ties) {
		ties = filterByNewProfessors(ties);
		ties = filterByTimeBetweenCourses(ties);
		ties = filterByProfessorsWithHalfMax(ties);
		ties = filterByNewCourses(ties);
		ties = filterBySpecificRoomCourses(ties);
		LOGGER.finer("Still a " + ties.size() + " way tie");
		return ties.get(0);
	}

	/**
	 * Course tiebreaker.
	 *
	 * @param ties the ties
	 * @return the preference
	 */
	protected Preference courseTiebreaker(List<Preference> ties) {
		ties = filterByNewProfessors(ties);
		ties = filterByTimeBetweenCourses(ties);
		ties = filterByProfessorsWithHalfMax(ties);
		ties = filterByNewCoursesForProfessor(ties);
		return ties.get(0);
	}

	/**
	 * Professor tiebreaker.
	 *
	 * @param professor the professor
	 * @param ties the ties
	 * @return the preference
	 */
	protected Preference professorTiebreaker(Professor professor, List<Preference> ties) {
		List<Preference> preferences = new ArrayList<Preference>();
		if(!professor.getTimeBetweenCourses().equals("No preference")) {
			for(int i=0;i<ties.size();i++) {
				String timeslot = ties.get(i).getItem().split("::")[1];
				if(isOptimalTimeslot(timeslot, professor.getTimeBetweenCourses())) {
					preferences.add(ties.get(i));
				}
			}
		}
		if(preferences.size()>0) {
			return preferences.get(0);
		}
		return ties.get(0);
	}

	/**
	 * Filter <code>ties</code> by professors with half max courses.
	 *
	 * @param ties the ties
	 * @return the filtered list
	 */
	protected List<Preference> filterByProfessorsWithHalfMax(List<Preference> ties) {
		List<Preference> preferences = new ArrayList<Preference>();
		for(int i=0;i<ties.size();i++) {
			Preference preference = ties.get(i);
			Professor professor = (Professor) system.getObject(preference.getItem().split("::")[1].split("::")[0], system.getProfessors());
			int halfMax = professor.getMaxCourses()/2;
			if(professor.getAssignedCourses()<halfMax) {
				preferences.add(preference);
			}
		}
		if(preferences.size()==0) {
			return ties;
		}
		return preferences;
	}

	/**
	 * Filters <code>ties</code> based on professors which have a time between courses preference.
	 *
	 * @param ties the ties
	 * @return professors which have a time between courses preference
	 */
	protected List<Preference> filterByTimeBetweenCourses(List<Preference> ties) {
		List<Preference> preferences = new ArrayList<Preference>();
		for(int i=0;i<ties.size();i++) {
			Preference preference = ties.get(i);
			Professor professor = (Professor) system.getObject(preference.getItem().split("::")[1].split("::")[0], system.getProfessors());
			if(!professor.getTimeBetweenCourses().equals("No preference")) {
				preferences.add(preference);
			}
		}
		if(preferences.size()==0) {
			return ties;
		}
		return preferences;
	}

	/**
	 * Filter <code>ties</code> by new courses.
	 *
	 * @param ties the ties
	 * @return the filtered list
	 */
	protected List<Preference> filterByNewCourses(List<Preference> ties) {
		List<Preference> preferences = new ArrayList<Preference>();
		for(int i=0;i<ties.size();i++) {
			Preference preference = ties.get(i);
			Course course = (Course) system.getObject(preference.getItem().split("::")[0], system.getCourses());
			boolean newCourse = true;
			for(AssignedCourse assignedCourse : schedule.getCourses()) {
				if(course.getName().equals(assignedCourse.getName())) {
					newCourse = false;
				}
			}
			if(newCourse) {
				preferences.add(preference);
			}
		}
		if(preferences.size()==0) {
			return ties;
		}
		return preferences;
	}

	/**
	 * Filter <code>ties</code> by new courses for professor.
	 *
	 * @param ties the ties
	 * @return the filtered list
	 */
	protected List<Preference> filterByNewCoursesForProfessor(List<Preference> ties) {
		List<Preference> preferences = new ArrayList<Preference>();
		for(int i=0;i<ties.size();i++) {
			Preference preference = ties.get(i);
			Course course = (Course) system.getObject(preference.getItem().split("::")[0], system.getCourses());
			Professor professor = (Professor) system.getObject(preference.getItem().split("::")[1].split("::")[0], system.getProfessors());
			boolean newCourse = true;
			for(AssignedCourse assignedCourse : schedule.getCourses()) {
				if(course.getName().equals(assignedCourse.getName()) && professor.getName().equals(assignedCourse.getProfessor())) {
					newCourse = false;
				}
			}
			if(newCourse) {
				preferences.add(preference);
			}
		}
		if(preferences.size()==0) {
			return ties;
		}
		return preferences;
	}

	/**
	 * Filter <code>ties</code> by courses in a specific room.
	 *
	 * @param ties the ties
	 * @return the filtered list
	 */
	protected List<Preference> filterBySpecificRoomCourses(List<Preference> ties) {
		List<Preference> preferences = new ArrayList<Preference>();
		for(int i=0;i<ties.size();i++) {
			Preference preference = ties.get(i);
			Course course = (Course) system.getObject(preference.getItem().split("::")[0], system.getCourses());
			if(!course.getRoomPreference().equals("Any")) {
				preferences.add(preference);
			}
		}
		if(preferences.size()==0) {
			return ties;
		}
		return preferences;
	}

	/**
	 * Checks if is optimal timeslot.
	 *
	 * @param timeslot the timeslot
	 * @param tbc the value
	 * @return true, if is optimal timeslot
	 */
	protected boolean isOptimalTimeslot(String timeslot, String tbc) {
		Date time = timeslotToDate(timeslot);
		Date ten = timeslotToDate("DAY 10:00");
		Date three = timeslotToDate("DAY 3:00");
		if(tbc.equals("1 to 3")) {
			if(time.after(ten) && time.before(three)) return true;
			else return false;
		}
		if(tbc.equals("6 or more")) {
			if(time.before(ten) || time.after(three)) return true;
			else return false;
		}
		return true;
	}

	/**
	 * Checks to make sure there are no conflicting courses for a given timeslot.
	 *  
	 * @param course The course to be assigned
	 * @param timeslot The timeslot to check
	 * @return true if timeslot is ok, false if it is conflicting
	 */
	protected boolean hasNoConflictingCourse(Course course, String timeslot) {
		List<String> courseNames = new ArrayList<String>();
		for(AssignedCourse assignedCourse : schedule.getCourses()) {
			if(assignedCourse.getTimeslot().equals(timeslot)) {
				courseNames.add(assignedCourse.getName());
			}
		}
		int num = Integer.parseInt(course.getNumber().substring(0, 3));
		for(int i=0;i<courseNames.size();i++) {
			int assignedNum = Integer.parseInt(courseNames.get(i).substring(4, 7));
			if(isTimeslotConflict(assignedNum, num)) {
				return false;
			}
		}
		return true;
	}

	/**
	 * Checks if two courses are allowed to be at the same time.<br>
	 * Currently:<br>
	 * -No classes with same number at same time.<br>
	 * -Classes over 399 cannot be at same time.<br>
	 * -Classes between 199 & 400 cannot be at the same time.<br>
	 * -Also see {@link #isGradConflict(int, int)}
	 * 
	 * @param assignedNum number of the assigned course
	 * @param num number of the conflicting course
	 * @return true, if there is a conflict, false if not
	 */
	private boolean isTimeslotConflict(int assignedNum, int num) {
		if(num==assignedNum) {
			return true;
		}
		if(isGradConflict(assignedNum, num)) {
			return true;
		}
		if(num>399 && assignedNum>399) {
			return true;
		}
		if(num>199 && num<400 && assignedNum>199 && assignedNum<400) {
			return true;
		}
		return false;
	}

	/**
	 * Grad students often teach low level classes.  This method makes sure
	 * graduate level classes (>499) don't conflict with (<200) level classes.
	 * 
	 * @param assignedNum number of the assigned course
	 * @param num number of the conflicting course
	 * @return true if there is a conflict, false if there is not
	 */
	private boolean isGradConflict(int assignedNum, int num) {
		if(num<200 && assignedNum>499) {
			return true;
		}
		if(num>499 && assignedNum<200) {
			return true;
		}
		return false;
	}

	/**
	 * Takes a proposed <code>Timeslot</code> and compares it to each previously assigned course
	 * for that professor.  If all previous timeslots pass the {@link #isInRange(int, String)} check
	 * a score of 100 is returned, otherwise 0 is returned. 
	 *
	 * @param schedule the schedule
	 * @param professor the professor
	 * @param timeslot the timeslot
	 * @return the value, either 0 or 100
	 */
	protected int timeBetweenCoursesValue(Schedule schedule, Professor professor, String timeslot) {
		//TODO Give half credit for times a range away?
		String tbc = professor.getTimeBetweenCourses();
		if(professor.getAssignedCourses().equals(0) || tbc.equals("No preference")) {
			return 100;
		}
		int value = 0;
		for(AssignedCourse course : schedule.getCourses()) {
			if(course.getProfessor().equals(professor.getName()) && !course.getTimeslot().equals(timeslot)) {
				String assignedTimeslot = course.getTimeslot();
				int difference = 0;
				if(timeslot.split(" ")[0].equals(assignedTimeslot.split(" ")[0])) {
					Date date1 = timeslotToDate(timeslot);
					Date date2 = timeslotToDate(assignedTimeslot);
					long differenceMillis = date2.getTime() - date1.getTime();
					difference = (int) (((differenceMillis/1000)/60)/60);
					difference = Math.abs(difference);
				}
				else {
					difference = 12;
				}
				String msg = "Proposed: " + timeslot + " Assigned: " + assignedTimeslot + " Difference: " + difference + " TBC: " + tbc;
				LOGGER.finest(msg);
				if(isInRange(difference, tbc)) {
					value = 100;
				}
				else {
					return 0;
				}				
			}
		}
		return value;
	}

	/**
	 * Checks if is in range.
	 *
	 * @param difference the difference
	 * @param tbc the tbc
	 * @return true, if is in range
	 */
	private boolean isInRange(int difference, String tbc) {
		if(tbc.equals("1 to 3") && difference<=3 && difference>0) {
			return true;
		}
		else if(tbc.equals("3 to 6") && difference>=3 && (difference<=6 || difference==12)) {
			return true;
		}
		else if(tbc.equals("6 or more") && difference>=6) {
			return true;
		}
		return false;
	}

	/**
	 * Timeslot to date.
	 *
	 * @param timeslot the timeslot
	 * @return the date
	 */
	protected Date timeslotToDate(String timeslot) {
		String time = timeslot.split(" ")[1];
		time = time.split("-")[0];
		if(isMorning(time)) {
			time = time + " AM";
		}
		else {
			time = time + " PM";
		}
		SimpleDateFormat sdf = new SimpleDateFormat("hh:mm aa");
		Date date = null;
		try {
			date = sdf.parse(time);
		} catch (ParseException e) {
			String msg = "Error in timeslotToDate: " + e.toString();
			LOGGER.warning(msg);
			prompts.nonFatalError(msg);
		}
		return date;
	}

	/**
	 * Checks if <code>time</code> is in the morning.
	 *
	 * @param time the time
	 * @return true, if is morning
	 */
	private boolean isMorning(String time) {
		if(time.contains("8") || time.contains("9") || time.contains("10") || time.contains("11")) {
			return true;
		}
		return false;
	}

	/**
	 * Assigns all manually assigned courses.
	 */
	protected void manuallyAssignCourses() {
		Schedule schedule = system.getMasterSchedule();
		for(AssignedCourse course : schedule.getCourses()) {
			String assignment = course.getSectionNumber() + "::" + course.getProfessor() + "::" +
					course.getRoom() + "::" + course.getTimeslot();
			Preference preference = new Preference();
			preference.setItem(assignment);
			preference.setValue(0);
			assign(preference);
		}
	}

	/**
	 * Assigns a course. 
	 *
	 * @param preference the preference; format for item is: <code>sectionNumber::professorName::roomName::timeslot</code>
	 */
	protected void assign(Preference preference) {
		String[] assignment = preference.getItem().split("::");
		String courseSection = assignment[0];
		String professorName = assignment[1];
		String roomName = assignment[2];
		String timeslot = assignment[3];
		Course course = (Course) system.getObject(courseSection, system.getCourses());
		AssignedCourse assignedCourse = new AssignedCourse();
		assignedCourse.setName(course.getName());
		assignedCourse.setRoom(roomName);
		assignedCourse.setProfessor(professorName);
		assignedCourse.setEnrollment(course.getEnrollment());
		assignedCourse.setSectionNumber(course.getSectionNumber());
		assignedCourse.setTimeslot(timeslot);
		Professor professor = (Professor) system.getObject(professorName, system.getProfessors());
		professor.setAssignedCourses(professor.getAssignedCourses()+1);
		for(Room room : system.getRooms()) {
			if(room.getName().equals(roomName)) {
				room.removeTimeslot(timeslot);
			}
		}
		String msg = "Assigning course " + course.getName() + " Section: " + course.getSectionNumber() + " To: " + professorName + " In: " + roomName + " At: " + timeslot
				+ "\nExpected value: " + preference.getValue();
		LOGGER.fine(msg);
		system.removeCourse(course);
		if(course.getHasLab()) {
			setLab(assignedCourse);
		}
		schedule.addCourse(assignedCourse);
		updateProgress();
	}

	/**
	 * Update progress for the progress bar.
	 */
	protected void updateProgress() {
		int percent = (int) (((float) processingProgress / (float) processingTotal)*100);
		LOGGER.finer("Progress: " + processingProgress + " Total: " + processingTotal + " Percent: " + percent);
		setProgress(percent);
		processingProgress++;
	}

	/**
	 * Gets the theoretical max value of {@link #schedule}.
	 *
	 * @return the theoretical max
	 */
	protected Integer getTheoreticalMax() {
		int total = 0;
		List<Preference> coursePreferences = new ArrayList<Preference>();
		for(Professor professor : system.getProfessors()) {
			for(Preference preference : professor.getPreferences()) {
				String item = preference.getItem();
				Integer value = preference.getValue();
				if(system.getObject(item, system.getTimeslots())!=null) {
					total = total + Math.abs(value);
				}
				else if(system.getObject(item, system.getRooms())!=null) {
					if(value<0) {
						total = total + Math.abs(value);
					}
					else {
						total = total + value * professor.getMaxCourses();	
					}
				}
				else {
					total = total + getCourseValue(coursePreferences, preference);
				}
			}
		}
		total = total + processCourseMaximums(coursePreferences);
		//Includes time between courses
		total = total + system.getCourses().size() * 100;
		return total;
	}

	/**
	 * Gets the course value.
	 *
	 * @param coursePreferences the course preferences
	 * @param preference the preference
	 * @return the course value
	 */
	private int getCourseValue(List<Preference> coursePreferences, Preference preference) {
		//Professor max courses may be a possible limitation, for now it's being ignored.
		Integer value = preference.getValue();
		int total = 0;
		if(value<0) {
			total = total + Math.abs(value);
		}
		else if(coursePreferences.contains(preference)) {
			int index = coursePreferences.indexOf(preference);
			Preference cp = coursePreferences.get(index);
			if(cp.getValue()<preference.getValue()) {
				cp.setValue(preference.getValue());
			}
		}
		else {
			coursePreferences.add(preference);
		}
		return total;
	}

	/**
	 * Process course maximums.
	 *
	 * @param coursePreferences the course preferences
	 * @return the int
	 */
	private int processCourseMaximums(List<Preference> coursePreferences) {
		int total = 0;
		for(Preference preference : coursePreferences) {
			String item = preference.getItem();
			Integer value = preference.getValue();
			total = total + value * getCourseNameCount(item);
		}
		return total;
	}

	/**
	 * Gets the highest value keys.
	 *
	 * @param map the map
	 * @return the highest value keys
	 */
	protected List<Preference> getHighestValueKeys(HashMap<String, Integer> map) {
		List<Preference> keys = new ArrayList<Preference>();
		Integer maxScore = 0;
		Iterator<Entry<String, Integer>> it = map.entrySet().iterator();
		while (it.hasNext()) {
			Map.Entry<String, Integer> pairs = (Map.Entry<String, Integer>)it.next();
			Integer myScore = pairs.getValue();
			Preference preference = new Preference();
			preference.setItem(pairs.getKey());
			preference.setValue(myScore);
			if(myScore > maxScore) {
				maxScore = myScore;
				keys.clear();
				keys.add(preference);
			}
			else if(myScore.equals(maxScore)) {
				keys.add(preference);
			}
		}
		return keys;
	}

	/**
	 * Sleeps the thread for 100 milliseconds.  If this isn't called and the algorithm 
	 * finishes extremely fast, {@link #done()} isn't called properly. 
	 */
	private void delay() {
		try {
			Thread.sleep(100);
		} catch (InterruptedException e) {
			LOGGER.fine("User cancelled algorithm");
		}
	}

	/**
	 * Counts the number of courses with a given name.
	 * 
	 * @param name The course name to be counted
	 * @return the count
	 */
	private int getCourseNameCount(String name) {
		int count = 0;
		for(Course course : system.getCourses()) {
			if(course.getName().equals(name)) {
				count++;
			}
		}
		return count;
	}

	/**
	 * Gets the room timeslot map.
	 *
	 * @param professor the professor
	 * @param course the course
	 * @return the room timeslot map
	 */
	protected HashMap<String, Integer> getRoomTimeslotMap(Professor professor, Course course) {
		HashMap<String, Integer> roomTimeslotValues = new HashMap<String, Integer>();
		for(Room room : system.getRooms()) {
			if(course.getEnrollment()<=room.getCapacity() || room.getCapacity().equals(0)) {
				Integer roomValue = system.getPreferenceValue(professor, room.getName());
				if(course.getRoomPreference().equals(room.getName()) || (course.getRoomPreference().equals("Any") && !room.getLab())) {
					checkTimeslots(professor, course, roomTimeslotValues, room, roomValue);
				}
			}
		}
		return roomTimeslotValues;
	}

	/**
	 * Check timeslots.
	 *
	 * @param professor the professor
	 * @param course the course
	 * @param roomTimeslotValues the room timeslot values
	 * @param room the room
	 * @param roomValue the room value
	 */
	private void checkTimeslots(Professor professor, Course course, HashMap<String, Integer> roomTimeslotValues, Room room, Integer roomValue) {
		for(String timeslot : room.getTimeslots()) {
			Integer value = roomValue + system.getPreferenceValue(professor, timeslot);
			String key = room.getName() + "::" + timeslot;
			if(hasNoConflictingCourse(course, timeslot)  && checkTimeslot(professor, timeslot)) {
				int tbcValue = timeBetweenCoursesValue(schedule, professor, timeslot);
				value = value + tbcValue;
				roomTimeslotValues.put(key, value);
			}
		}
	}

	/**
	 * Filter <code>ties</code> by new professors.
	 *
	 * @param ties the ties
	 * @return the filtered list
	 */
	protected List<Preference> filterByNewProfessors(List<Preference> ties) {
		List<Preference> preferences = new ArrayList<Preference>();
		for(int i=0;i<ties.size();i++) {
			Preference preference = ties.get(i);
			Professor professor = (Professor) system.getObject(preference.getItem().split("::")[1].split("::")[0], system.getProfessors());
			if(professor.getAssignedCourses().equals(0)) {
				preferences.add(preference);
			}
		}
		if(preferences.size()==0) {
			return ties;
		}
		return preferences;
	}

	/**
	 * Gets the schedule value.
	 *
	 * @param schedule the schedule
	 * @return the schedule value
	 */
	protected int getScheduleValue(Schedule schedule) {
		LOGGER.finer("Getting schedule value.");
		int value = 0;
		system.resetVariables();
		for(AssignedCourse course : schedule.getCourses()) {
			int cValue = 0;
			Professor professor = (Professor) system.getObject(course.getProfessor(), system.getProfessors());
			cValue = timeBetweenCoursesValue(schedule, professor, course.getTimeslot());
			cValue = cValue + system.getPreferenceValue(professor, course.getName());
			cValue = cValue + system.getPreferenceValue(professor, course.getRoom());
			cValue = cValue + system.getPreferenceValue(professor, course.getTimeslot());
			professor.setAssignedCourses(professor.getAssignedCourses()+1);
			LOGGER.fine("Course " + course.getSectionNumber() + " value: " + cValue);
			value = value + cValue;
		}
		for(Professor professor : system.getProfessors()) {
			for(Preference preference : professor.getPreferences()) {
				if(preference.getValue()<0 && !isAssigned(schedule, professor, preference.getItem())) {
					int pValue = Math.abs(preference.getValue());
					LOGGER.fine(professor.getName() + " is not assigned " + preference.getItem() + " adding " + pValue);
					value = value + pValue;
				}
			}
		}
		return value;
	}

	protected boolean isAssigned(Schedule schedule, Professor professor, String item) {
		for(AssignedCourse course : schedule.getCourses()) {
			if(course.getProfessor().equals(professor.getName())) {
				if(course.getName().equals(item) || course.getRoom().equals(item) || course.getTimeslot().equals(item)) {
					return true;
				}
			}
		}
		return false;
	}

	/**
	 * Sets the lab.
	 *
	 * @param course the new lab
	 */
	protected void setLab(AssignedCourse course) {
		course.setLab("");
		//TODO Fill this in
	}

	/**
	 * Processes actions when progress bar closed by user.
	 */
	public void progressBarClosed() {
		String msg = "Are you sure you want to cancel?";
		msg = msg + " " + seed + " schedules processed.";
		if(bestSchedule==null) {
			msg = msg + " No valid schedules found yet.";
		}
		else {
			msg = msg + " Highest value schedule so far: " + bestSchedule.getValue();
		}
		if(prompts.confirm(msg)) {
			cancel(true);
		}
	}

	/* (non-Javadoc)
	 * @see javax.swing.SwingWorker#doInBackground()
	 */
	@Override
	final protected Void doInBackground() {
		try {
			if(!validator.preValidate()) {
				String msg = "Schedule prevalidation failed, aborting schedule generation.";
				LOGGER.info(msg);
				prompts.nonFatalError(msg);	
			}
			else {
				start();
			}
		} catch(Exception e) {
			e.printStackTrace();
		}
		Thread.interrupted();
		Frame.getInstance().killProgressBar();
		delay();
		return null;
	}

	/* (non-Javadoc)
	 * @see javax.swing.SwingWorker#done()
	 */
	@Override
	protected void done() {
		if(algorithmName!=null) {
			if(bestSchedule!=null) {
				String msg = "";
				if(bestSchedule.getValue().equals(bestSchedule.getTheoreticalMax())) {
					msg = "Processed " + seed + " schedules before finding maximum value schedule.";
				}
				else {
					msg = "Out of " + seed + " processed schedules, best value is: " + bestSchedule.getValue() + ".";
				}
				LOGGER.info(msg);
				prompts.message(msg);
				Frame.getInstance().addSchedule(bestSchedule);
			}
			else {
				String msg = "No valid schedules found after processing " + this.seed + " schedules.";
				LOGGER.info(msg);
				prompts.message(msg);
			}
		}
	}
}
